package a_doubleWrite;

import java.util.ArrayList;
import java.util.List;

/**
 * 131.132 分割回文串2
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。
 * 返回 s 所有可能的分割方案。
 * <p>
 * 回文串 是正着读和反着读都一样的字符串。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-26 14:42
 */
public class L131 {
    boolean[][] dp;
//    dfs超时
//    int min=Integer.MAX_VALUE;
//    public void dfs(String s, int sum, int index,boolean[][] dp) {
//        if (index == s.length()) {
//            min=Math.min(sum, min);
//            return;
//        }
//        for (int i = index; i < s.length(); i++) {
//            if (!dp[index][i]) continue;
//            sum++;
//            dfs(s, sum, i+1,dp);
//            sum--;
//        }
//    }

    private void isValidDp(String s1) {
        dp=new boolean[s1.length()][s1.length()];
        for (int j = 0; j <s1.length() ; j++) {
            for (int i = j; i >=0 ; i--) {
                if(i==j){//一个数
                    dp[i][j]=true;
                }else if(j-i==1){
                    //两位数
                    dp[i][j]=(s1.charAt(i)==s1.charAt(j));
                }else{
                    //三位数以上
                    dp[i][j]=(s1.charAt(i)==s1.charAt(j))&&dp[i+1][j-1];
                }
            }
        }
    }

    public int minCut(String s) {
        isValidDp(s);

        //dp[i]代表0-i 最少分割次数 。
        int[] dp2=new int[s.length()];
        for (int i = 0; i <s.length() ; i++) {
            if(dp[0][i]){//0-i是回文,无需分割
                dp2[i]=0;
            }else {
                dp2[i]=i;
                for (int j = 0; j <i ; j++) {
                    if(dp[j+1][i]){
                        dp2[i]=Math.min(dp2[i],dp2[j]+1);
                    }
                }
            }
        }
        return dp2[s.length()-1];
    }

    public static void main(String[] args) {
        L131 l131 = new L131();
        int ssa = l131.minCut("ab");
        System.out.println(ssa);
    }
}
